from collections import deque
from typing import List, Optional

from python.mypackage.TreeNode import TreeNode


class Solution:
    """
     方法： 使用双端队列实现二叉树的锯齿形层序遍历
     
     Args:
         root: Optional[TreeNode] - 二叉树的根节点
     
     Returns:
         List[List[int]]: 锯齿形层序遍历结果,每个子列表包含同一层的节点值
     
     Time: O(n) - 其中n是二叉树的节点数，每个节点只被访问一次
     
     Space: O(w) - 其中w是二叉树的最大宽度，队列中最多存储一层的所有节点
     """
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        ans = []
        q = deque([root])
        while q:
            level_size = len(q)
            level_list = deque()
            for _ in range(level_size):
                node = q.popleft()
                if(len(ans) % 2 == 0):
                    level_list.append(node.val)
                else:
                    level_list.appendleft(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            ans.append(list(level_list))
        return ans